/**
 * Created With IntelliJ IDEA
 * Description:牛客网:BM39 序列化二叉树
 * <a href="https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84?tpId=295&tqId=23455&ru=/exam/company&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Fcompany">...</a>
 * User: DELL
 * Data: 2023-04-15
 * Time: 23:42
 */

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

/**
 * 因为题目为自定义规则,这里就根据 前序遍历 序列化和反序列化
 */
public class Solution {
    /**
     * 根据 前序遍历 序列化
     * 根据题目中规定的每个结点的值为 0 <= x <= 150 制定如下规则
     * 规则:空结点用 '#' 表示,其余结点的值均用三位数字字符表示,不够三位的前补 '0'
     * @param root
     * @return
     */
    public String Serialize(TreeNode root) {
        StringBuffer res = new StringBuffer();
        preorderSerialize(root,res);
        return res.toString();
    }

    private void preorderSerialize(TreeNode root, StringBuffer res) {
        if (root == null) {
            res.append("#");
            return;
        }
        //根结点
        //不够三位的前补 '0'
        if (root.val < 10) {
            res.append("00");
        } else if (root.val < 100) {
            res.append("0");
        }
        res.append(root.val);
        //左子树
        preorderSerialize(root.left,res);
        //右子树
        preorderSerialize(root.right,res);
        return;
    }

    /**
     * 根据序列化规则反序列化该二叉树
     * @param str
     * @return
     */
    public TreeNode Deserialize(String str) {
        if (str == null || str.length() == 0) {
            return null;
        }
        return preorderDeserialize(str);
    }

    private int index = 0;
    private TreeNode preorderDeserialize(String str) {
        if (str.charAt(index) == '#') {
            index += 1;
            return null;
        }
        //根节点
        TreeNode node = new TreeNode(Integer.parseInt(str.substring(index,index+3)));
        index += 3;
        //左子树
        node.left = preorderDeserialize(str);
        //右子树
        node.right = preorderDeserialize(str);
        return node;
    }
}